# 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
#  在「杨辉三角」中，每个数是它左上方和右上方的数的和。
#
#  示例 1:
# 输入: numRows = 5
# 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
#
#  示例 2:
# 输入: numRows = 1
# 输出: [[1]]
#
#
from typing import List


class Solution:
    def generate2(self, numRows: int) -> List[List[int]]:
        """
        动态规划
        状态转移方程:dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
        """
        dp = []
        for i in range(numRows):
            cur_row = []
            for j in range(i + 1):
                if j == 0 or j == i:
                    cur_row.append(1)
                else:
                    cur_row.append(dp[-1][j - 1] + dp[-1][j])
            dp.append(cur_row)
        return dp

    def generate1(self, numRows: int) -> List[List[int]]:
        if numRows == 1:
            return [[1]]
        if numRows == 2:
            return [[1], [1, 1]]
        res = [[1], [1, 1]]
        for i in range(1, numRows - 1):
            row, pre_row = [], res[-1]
            for j in range(i):
                row.append(pre_row[j] + pre_row[j + 1])
            res.append([1] + row + [1])
        return res

    def generate(self, numRows: int) -> List[List[int]]:
        return self.generate2(numRows)


if __name__ == '__main__':
    print(Solution().generate(5))
